#pragma once

#include <assert.h>
#include <vector>

namespace ly
{
	template<class T>
	class Less
	{
	public:
		bool operator()(T a, T b)
		{
			return a < b;
		}
	};

	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		priority_queue(){}

		template<class inputiterator>
		priority_queue(inputiterator first, inputiterator last)
			:_con(first, last)
		{}

		bool empty() const
		{
			return _con.empty();
		}

		size_t size() const
		{
			return _con.size();
		}

		const T& top() const
		{
			assert(size() > 0);

			return _con[0];
		}

		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if(_comp(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(size()-1);
		}

		void adjust_down(int parent)
		{
			int child = parent * 2 + 1, n = size();

			while (child < n)
			{
				if (child + 1 < n && _comp(_con[child], _con[child + 1]))
				{
					child++;
				}

				if (_comp(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 - 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			std::swap(_con[0], _con[size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
	private:
		Container _con;
		Compare _comp;
	};
}
